package com.gxc.sort;

import com.gxc.randomArray.generateRandomArray;

/**
 * 堆排序
 */
public class heap {

    public static void main(String[] args) {
        int[] arr = generateRandomArray.generateArray(20, 30);

        generateRandomArray.sout(arr);

        heapSort(arr);

        System.out.println("=======排序后=====");

        generateRandomArray.sout(arr);
    }

    /**
     * 堆排序
     * @param arr
     */
    private static void heapSort(int[] arr) {
        //构件初始大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        //更快的构件大根堆
        for (int i = arr.length-1; i >=0; i--) {
            heapify(arr, i, arr.length);
        }


        System.out.println("--------------------");

        int heapszie = arr.length;
        generateRandomArray.swap(arr, 0, --heapszie);
        while (heapszie>0) {
            heapify(arr, 0, heapszie);
            generateRandomArray.swap(arr, 0, --heapszie);
        }
    }

    private static void heapify(int[] arr, int index, int heapszie) {
        //左子节点
        int left = 2*index+1;
        while (left<heapszie) {
            //左右子节点比较大小
            int largest = left+1<heapszie && arr[left]<arr[left+1]?left+1:left;
            //左右子节点大数和父节点比较
            largest = arr[largest]<arr[index]?index:largest;

            if(largest == index) break;

            generateRandomArray.swap(arr, index, largest);
            index = largest;
            left = 2*index+1;
        }
    }

    private static void heapInsert(int[] arr, int index) {
        while (arr[index]>arr[(index-1)/2]) {
            generateRandomArray.swap(arr, index, (index-1)/2);
            index = (index-1)/2;
        }
    }
}
